
package arithmetic.sort;


/**
 * 快排
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] nums = {5, 4, 6, 3, 2, 0, 9};
        int sum = 0;
        //使用快速排序
        QuickSort.quitSort(nums, 0, nums.length - 1);
        //有序数组取偶数下标累加
        for (int i = 0; i < nums.length; i++) {
            if ((i & 1) == 1) {
                sum += nums[i];
            }
        }
        System.out.println(sum);
    }

    /**
     * 快排实现
     *
     * @param nums
     * @param left
     * @param right
     */
    public static void quitSort(int[] nums, int left, int right) {
        //1 定义1个基准值（取第一数），定义2个指针，分别指向头和尾
        //2 从两边往中间移动，左边找第一个比基准值大的值，右边找第一个比基准值小的值，找到后交换
        //3 当左右指针相遇则代表第一轮排序完毕，和基准值交换，这个基准值就排在最终的位置了
        //4 左边所有值都比基准值小，右边所有值比基准值大。对左右两边数组递归
        //5 类似二叉树的中序遍历，递归左右子树
        if (left >= right) {
            return;//数组只有1个元素直接返回
        }
        int low = left;
        int high = right;
        int base = nums[left];
        //当low=high，第一次排序完成
        while (low < high) {
            //递减直到找到base>num[high]
            while (base >= nums[high] && low < high) {
                high--;
            }
            //递增直到找到base<num[low]
            while (base <= nums[low] && low < high) {
                low++;
            }
            //交换两个值
            if (low < high) {
                int temp = nums[high];
                nums[high] = nums[low];
                nums[low] = temp;
            }
        }
        nums[left]=nums[low];
        nums[low] = base;

        //递归
        quitSort(nums, left, low - 1);
        quitSort(nums, low + 1, right);
    }
}